package main

import "fmt"

func main() {
	node := &ListNode{
		Val: 1,
		Next: &ListNode{
			Val: 2,
			Next: &ListNode{
				Val: 3,
				Next: &ListNode{
					Val:  4,
					Next: nil,
				},
			},
		},
	}
	printNode(node)
	reversed := reverseList(node)
	printNode(reversed)

}

func printNode(node *ListNode) {
	cur := node
	for {
		if cur == nil {
			break
		}
		fmt.Printf(fmt.Sprintf("%d->", cur.Val))
		cur = cur.Next
	}
	fmt.Printf("null\n")
}

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	newHead := reverseList(head.Next)
	head.Next.Next = head
	head.Next = nil
	return newHead
}
